#include <iostream>
#include <cstdlib>
using namespace std;

struct Item {
    void SetItem(int w, int v, bool s) {
        weight = w;
        value = v;
        selected = s;
    }
    int weight;
    int value;
    bool selected;
};


int Pick(Item goods[],int totalWeight,int amount) {
    int c[amount + 1][totalWeight + 1];

    for(int i = 0; i < amount + 1; ++i) c[i][0] = 0;
    for(int j = 0; j < totalWeight + 1; ++j) c[0][j] = 0;

    for(int i = 1; i < amount + 1; ++i)
        for(int j = 1; j < totalWeight + 1; ++j) {
            if(goods[i].weight < j + 1)
                c[i][j] = max(c[i - 1][j], c[i - 1][j - goods[i].weight] + goods[i].value);
            else
                c[i][j] = c[i - 1][j];
        }

    for(int i = 0; i < amount + 1; ++i) {
        for(int j = 0; j < totalWeight + 1; ++j) {
            cout<<"\t"<<c[i][j]<<" ";
        }
        cout<<endl;
    }

    for(int i = amount, j = totalWeight; i > 0; --i) {
        if(c[i][j] > c[i - 1][j]) {
            goods[i].selected = true;
            j = j - goods[i].weight;
        }
    }

    return c[amount][totalWeight];

}

int main() {
    int amount = 5;
    int totalWeight = 10;
    Item* goods = new Item[amount + 1];
    goods[0].SetItem(0, 0, false);
    goods[1].SetItem(2, 6, false);
    goods[2].SetItem(2, 3, false);
    goods[3].SetItem(6, 5, false);
    goods[4].SetItem(5, 4, false);
    goods[5].SetItem(4, 6, false);

    int value = Pick(goods, totalWeight, amount);

    cout<<"Max value is "<<value<<endl;
    cout<<"Good picked are :"<<endl;;
    for(int i = 0; i < amount + 1; ++i) {
        if(goods[i].selected)
            cout<<"index = "<<i<<" -> "<<"weight = "<<goods[i].weight<<" "<<"value = "<<goods[i].value<<endl;;
    }

    delete [] goods;
    return 0;
}
